package zijie;

/**
 * 在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
 *
 * 示例 1:
 *
 * 输入: [3,2,1,5,6,4] 和 k = 2
 * 输出: 5
 * 示例 2:
 *
 * 输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
 * 输出: 4
 */
public class FindKthLargest_215_29 {
    private int k;
    public int findKthLargest(int[] nums, int k) {
        if(nums==null || nums.length==0 || k<1 || k > nums.length ){
            return -1;
        }
        this.k = k-1;
        return quickSelect(nums,0,nums.length - 1);
    }

    public int quickSelect(int[] nums, int left, int right) {
        if (left == right) return nums[right];
        int index = partition(nums, left, right);
        if(index == k){
            return nums[index];
        }
        if (index < k) {
            return quickSelect(nums, index + 1, right);
        }else{
            return quickSelect(nums, left, index - 1);
        }
    }

    private  int partition(int[] arr, int startIndex, int endIndex) {
        int pivot = arr[startIndex];
        int left = startIndex;
        int right = endIndex;
        while ( left != right) {
            while (left<right && arr[right] < pivot){
                right--;
            }
            while ( left<right && arr[left] >= pivot) {
                left++;
            }
            if (left<right) {
                swap(arr,left,right);
            }
        }
        swap(arr,startIndex,left);
        return left;
    }
    public void swap(int[] nums,int i,int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    public static void main(String[] args) {
        int[] test = {3,1,4,5,2,5};
        FindKthLargest_215_29 findKthLargest_215_29 = new FindKthLargest_215_29();
        findKthLargest_215_29.findKthLargest2(test,2);
        System.out.println(1);
    }

    public int findKthLargest2(int[] nums, int k) {
        if(nums == null || nums.length == 0 || k < 0 || k > nums.length) return -1;

        this.k = k - 1;
        return quickSort(nums,0,nums.length - 1);
    }
    public int quickSort(int[] nums,int left,int right){
        if(left == right) return nums[left];
        int index = partition(nums,left,right);
        if(k == index){
            return nums[index];
        }
        // 这里是从大到小逆序， k > index说明需要往右找，因为右边的下标大于index。
        if(k > index){
           return quickSort(nums,index + 1,right);
        }else{
           return quickSort(nums,left,index - 1);
        }
    }

    public int partition2(int[] nums, int start,int end){

        int base = nums[start];
        int l = start;
        int r = end;
        while (l < r){
            while (l < r && nums[r] < base){
                r--;
            }
            while (l < r && nums[l] >= base){
                l++;
            }
            if(l < r){
                swap2(nums,l,r);
            }
        }
        swap2(nums,start,l);
        return l;
    }

    private void swap2(int[] nums, int a, int b){
        int tmp = nums[a];
        nums[a] = nums[b];
        nums[b] = tmp;
    }


}
